#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T &x){
	x=0;int f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	x*=f;
}
const int N=2e6+5;
int cid,T,n,k,a[N],c[N];
long long b[N];
#define i128 __int128
void print(i128 x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) print(x/10);
	putchar(x%10+48);
}
i128 ans;
inline void sol(int i){
	c[i]=min(a[i],a[i-1]);
	for(int j=i-1;j;--j) c[j]=min(a[j-1],a[j]-c[j+1]);
	for(int j=i+1;j<=n;++j) c[j]=min(a[j],a[j-1]-c[j-1]);
	i128 sum=0;
	for(int j=1;j<=n;++j){
		if(j<=k) sum+=(i128)b[j]*c[j];
		else if(j>=n-k+1) sum+=(i128)(b[k]-b[k-(n-j+1)])*c[j];
		else sum+=(i128)b[k]*c[j];
	}
	ans=max(ans,sum);
}
int main(){
	freopen("festival.in","r",stdin);
	freopen("festival.out","w",stdout);
	read(cid),read(T);
	while(T--){
		read(n),read(k);
		for(int i=1;i<n;++i) read(a[i]);
		a[0]=a[n]=1145141919;
		for(int i=1;i<=k;++i) read(b[i]),b[i]+=b[i-1];
		ans=-1;
		if(9<=cid&&cid<=11){
			sol(1);
		}else if(cid<=15&&cid!=7&&cid!=8) for(int i=1;i<=n;++i) sol(i);
		else{
			int len=max(2,(int)4e6/n*15);
			for(int i=1;i<=len&&i<=n;++i) sol(i);
			for(int i=n;n-i+1<=len&&i;--i) sol(i);
			for(int i=max(1,n/2-len+1);i<=n&&i<=n/2+len-1;++i) sol(i);
		}
		print(ans),putchar('\n');
	}
	return 0;
}

